#include <vector>
#include <climits>
#include <unordered_set>

using namespace std;

// 数组中两个数的最大异或值
// 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0<=i<=j<=n
// 1 <= nums.length <= 2 * 10^5
// 0 <= nums[i] <= 2^31 - 1
// 测试链接 : https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

class Solution 
{
private:
    // 准备这么多静态空间就够了，实验出来的
	// 如果测试数据升级了规模，就改大这个值
    static const int MAXN = 3000001;
    int tree[MAXN][2];
    int cnt;
    // 数字只需要从哪一位开始考虑
    int high;
    bool flag; // 标记最大值是否为 0

    // 求出二进制前导 0 的个数
    int numberOfLeadingZeros(int x)
    {
        for(int i = 0; i != 32; ++i)
        {
            if((x >> (31 - i)) & 1) return i;
        }
        return 32;
    }

    // 求出二进制尾随 0 的个数
    int numberOfTrailingZeros(int x)
    {
        for(int i = 0; i != 32; ++i)
        {
            if((x >> i) & 1) return i;
        }
        return 32;
    }

    void build(vector<int>& nums)
    {
        cnt = 1;
        // 找个最大值
        int mx = INT_MIN;
        for(int x : nums) mx = max(mx, x);
        if(mx == 0)
        {
            flag = true; // 最大值为 0，则直接返回
            return;
        }
        // 计算数组最大值的二进制状态，有多少个前缀的0
		// 可以忽略这些前置的 0，从 high 位开始考虑
        // __builtin_clz 返回输入数二进制表示从最高位开始的连续的 0 的个数
        // 但是不能给这个函数传入 0，否则将会报错
        // high = 31 - __builtin_clz(mx);
        high = 31 - numberOfLeadingZeros(mx);
        for(int x : nums) insert(x);
    }

    void insert(int x)
    {
        int cur = 1;
        for(int i = high, path; i >= 0; --i)
        {
            path = (x >> i) & 1;
            if(tree[cur][path] == 0)
            {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
        }
    }

    int maxXor(int x)
    {
        // 最终异或的结果(尽量大)
        int ans = 0;
        // 前缀树目前来到的节点编号
		int cur = 1;
        for(int i = high, want, status; i >= 0; --i)
        {
			// status : x 第 i 位的状态
            status = (x >> i) & 1;
            // want : x 第 i 位希望遇到的状态
            want = status ^ 1;
            if(tree[cur][want] == 0) // 询问前缀树，能不能达成
            {
                // 不能达成
                want ^= 1;
            }
            // want 变成真的往下走的路
            ans |= (status ^ want) << i;
            cur = tree[cur][want];
        }
        return ans;
    }

    // 使用的不是 tree 数组没有用 static 修饰，则不需要写这个方法
    void clear() 
    {
		for (int i = 1; i <= cnt; i++) 
        {
			tree[i][0] = tree[i][1] = 0;
		}
	}

public:
    // 前缀树的做法
    // 好想
    int findMaximumXOR1(vector<int>& nums) 
    {
        build(nums);
        if(flag) return 0; // 数组的最大值为 0，直接返回 0
        int ans = 0;
        for(int x : nums)
        {
            ans = max(ans, maxXor(x));
        }
        return ans;
    }

    // 哈希表的做法
    // 难想
    int findMaximumXOR2(vector<int>& nums) 
    {
        int mx = INT_MIN;
        for(int x : nums) mx = max(mx, x);
        if(mx == 0) return 0;

        int ans = 0;
        unordered_set<int> s;
        for(int i = 31 - __builtin_clz(mx); i >= 0; --i)
        {
            // ans : 31....i + 1 已经达成的目标
            int better = ans | (1 << i);
            s.clear();
            for(int x : nums)
            {
                // x : 31.....i 这些状态保留，剩下全成 0
                x = (x >> i) << i;
                s.insert(x);
                // x ^ 某状态 是否能达成 better 目标，就在 set 中找某状态 : better ^ x
                if(s.count(better ^ x))
                {
                    ans = better;
                    break;
                }
            }
        }
        return ans;
    }
};